package org.example.myleet.p639;

public class Solution {
    public int numDecodings(String s) {
        int mod = 1000000007;
        int n = s.length();
        //第0行代表该位数是与上一位数合并解析的方案数，第1行代表位数是单独解析的方案数
        long[][] dp = new long[2][n];
        //前一个字符
        char c_i_1 = s.charAt(0);
        //后一个字符
        char c_i;
        //默认第1个数组没有合并解析，只有单独解析
        dp[0][0] = 0;
        if (c_i_1 == '*') {
            //星号可以有9种解析
            dp[1][0] = 9;
        } else {
            if (c_i_1 == '0') {
                //如果第一个字符是0，则无解
                dp[1][0] = 0;
            } else {
                //某个确定的数字，1种解析
                dp[1][0] = 1;
            }
        }
        for (int i = 1; i < n; ++i) {
            c_i = s.charAt(i);
            //根据i-1位和i位是否*，有4种不同的大情况，每种大情况种包含有不同的小情况，分开讨论
            if (c_i_1 == '*') {
                if (c_i == '*') {
                    //情况1，i-1位和i位都是*
                    //针对合并解析进行分析
                    if (i > 1) {
                        //情况1-1，追溯第i-2位的方案数，并且对于1时，*有9种方案解析，对于2时，*有6种方案解析，加起来是15种方案解析
                        //而这15种情况是基于前一个星号属于单独解释时的方案数，前一个星号属于单独解释时的方案数 = i-2位的方案数
                        dp[0][i] = (dp[0][i - 2] + dp[1][i - 2]) * (9 + 6);
                    } else {
                        //情况1-2，第2位时，没有更前的字符可以追溯
                        dp[0][i] = 9 + 6;
                    }
                    //针对单独解析，则方案数等于i-1位的方案数，而*有9种方案解析，因此乘9
                    dp[1][i] = dp[0][i - 1] * 9 + dp[1][i - 1] * 9;
                } else {
                    //情况2，i-1位是*，i位是数字
                    if (i > 1) {
                        //情况2-1，i-1位的*前面还有字符
                        if (c_i < '7') {
                            //情况2-1-1，i位是1～6，因此i-1位的*可以解析为1或2，有两种解析
                            dp[0][i] = (dp[0][i - 2] + dp[1][i - 2]) * 2;
                        } else {
                            //情况2-1-2，i位是7～9，因此i-1位的*只可以解析为1，只有一种解析
                            dp[0][i] = dp[0][i - 2] + dp[1][i - 2];
                        }
                    } else {
                        //情况2-2，第2位时，没有更前的字符可以追溯，同样的推理看情况2-1
                        if (c_i < '7') {
                            dp[0][i] = 2;
                        } else {
                            dp[0][i] = 1;
                        }
                    }
                    if (c_i == '0') {
                        //情况2-3，第i位是0，则不能单独解析，因此单独解析的方案数为0
                        dp[1][i] = 0;
                    } else {
                        //针对单独解析，则方案数等于i-1位的方案数
                        dp[1][i] = dp[0][i - 1] + dp[1][i - 1];
                    }
                }
            } else {
                if (c_i == '*') {
                    //情况3，i-1位是数字，i位是*
                    if (c_i_1 < '3') {
                        if (c_i_1 == '1') {
                            //情况3-1，i-1位是1，则i位的合并解析有9种，11～19
                            dp[0][i] = dp[1][i - 1] * 9;
                        } else {
                            //情况3-2，i-1位是2，则i位的合并解析有6种，21～26
                            dp[0][i] = dp[1][i - 1] * 6;
                        }
                    } else {
                        //情况3-3，i-1位是3～9，则i位不能进行合并解析，合并解析方案数为0，
                        dp[0][i] = 0;
                    }
                    //针对单独解析，则方案数等于i-1位的方案数，而*有9种方案解析，因此乘9
                    dp[1][i] = dp[0][i - 1] * 9 + dp[1][i - 1] * 9;
                } else {
                    //情况4，i-1位和i位都是数字
                    if (c_i_1 < '3') {
                        if (c_i_1 == '1') {
                            //情况4-1，i-1位是1，则i位的合并解析有1种，两个数字都是确定的，方案数等于i-1位单独解析的方案数
                            dp[0][i] = dp[1][i - 1];
                        } else {
                            //情况4-2，i-1位是2
                            if (c_i < '7') {
                                //情况4-2-1，i位是1～6，可以与前一位做合并解析
                                dp[0][i] = dp[1][i - 1];
                            } else {
                                //情况4-2-2，i位是7～9，不可以与前一位做合并解析
                                dp[0][i] = 0;
                            }
                        }
                    } else {
                        //情况4-3，i-1位是3～7，则不能做合并解析
                        dp[0][i] = 0;
                    }
                    if (c_i == '0') {
                        //情况4-4，第i位为0，不能做单独解析
                        dp[1][i] = 0;
                    } else {
                        //情况4-5，第i为单独解析的方案数是i-1位的合并解析加上i-1位的单独解析
                        dp[1][i] = dp[0][i - 1] + dp[1][i - 1];
                    }
                }
            }
            //字符交换，为下一个巡航准备
            c_i_1 = c_i;
            //题目要求取模，因为数字可能会很大
            dp[0][i] %= mod;
            dp[1][i] %= mod;
        }
        //最后记得结果也要取模
        return (int) ((dp[0][n - 1] + dp[1][n - 1]) % mod);
    }
}
